{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Duplicates From an Unsorted Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteDuplicatesUnsorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从未排序的链表中移除重复元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个链表的第一个节点 <code>head</code> ，找到链表中所有出现<strong>多于一次</strong>的元素，并删除这些元素所在的节点。</p>\n",
    "\n",
    "<p>返回删除后的链表。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/21/tmp-linked-list.jpg\" style=\"width: 422px; height: 222px;\">\n",
    "<pre><strong>输入:</strong> head = [1,2,3,2]\n",
    "<strong>输出:</strong> [1,3]\n",
    "<strong>解释:</strong> 2 在链表中出现了两次，所以所有的 2 都需要被删除。删除了所有的 2 之后，我们还剩下 [1,3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/21/tmp-linked-list-1.jpg\" style=\"width: 422px; height: 151px;\">\n",
    "<pre><strong>输入:</strong> head = [2,1,1,2]\n",
    "<strong>输出:</strong> []\n",
    "<strong>解释:</strong> 2 和 1 都出现了两次。所有元素都需要被删除。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/21/tmp-linked-list-2.jpg\" style=\"width: 500px; height: 142px;\">\n",
    "<pre><strong>输入:</strong> head = [3,2,2,1,3,2,4]\n",
    "<strong>输出:</strong> [1,4]\n",
    "<strong>解释: </strong>3 出现了两次，且 2 出现了三次。移除了所有的 3 和 2 后，我们还剩下 [1,4] 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点个数的范围是 <code>[1, 10<sup>5</sup>]</code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-duplicates-from-an-unsorted-linked-list](https://leetcode.cn/problems/remove-duplicates-from-an-unsorted-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-duplicates-from-an-unsorted-linked-list](https://leetcode.cn/problems/remove-duplicates-from-an-unsorted-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2]', '[2,1,1,2]', '[3,2,2,1,3,2,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        cnts = defaultdict(int)\n",
    "        cur = head \n",
    "        while cur:\n",
    "            cnts[cur.val]+=1\n",
    "            cur = cur.next \n",
    "        cur1 = head \n",
    "        dummy = ListNode()\n",
    "        cur2 = dummy\n",
    "        while cur1:\n",
    "            if cnts[cur1.val] == 1:\n",
    "                cur2.next = cur1\n",
    "                cur2 = cur1 \n",
    "            cur1 = cur1.next \n",
    "        cur2.next = None \n",
    "\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        duplicateDict = dict()\n",
    "\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "\n",
    "        cur = head\n",
    "\n",
    "        while cur:\n",
    "            if cur.val in duplicateDict:\n",
    "                duplicateDict[cur.val] += 1\n",
    "            else:\n",
    "                duplicateDict[cur.val] = 1\n",
    "\n",
    "            cur = cur.next\n",
    "        \n",
    "        fast = head\n",
    "        slow = dummy\n",
    "        print(f'dict = {duplicateDict}')\n",
    "        \n",
    "        while fast:\n",
    "            if duplicateDict[fast.val] == 1:\n",
    "                slow.next = fast\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "            else:\n",
    "                # fast再遍历的时候，需要把所有的重复节点都跳过\n",
    "                while fast and duplicateDict[fast.val] > 1:\n",
    "                    fast = fast.next\n",
    "                # 要么fast 到最后\n",
    "                # 要么fast 到底一个不重复的node\n",
    "                slow.next = fast\n",
    "            \n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        d = defaultdict(int)\n",
    "        t = head \n",
    "        while t:\n",
    "            d[t.val] += 1\n",
    "            t = t.next\n",
    "        dummy = ListNode(0, head)\n",
    "        t = dummy\n",
    "        while t:\n",
    "            if t.next and d[t.next.val] > 1: t.next = t.next.next\n",
    "            else: t = t.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        b = ListNode(0, head)\n",
    "        d = {}\n",
    "        p = head\n",
    "        # 第一次遍历，查出重复的节点，\n",
    "        while p:\n",
    "            if p.val not in d:\n",
    "                d[p.val] = 1\n",
    "                b = b.next\n",
    "            else:\n",
    "                d[p.val] +=1\n",
    "                b.next = b = p.next\n",
    "            p = p.next\n",
    "        w = pr = ListNode(0, head)\n",
    "        \n",
    "        while head:\n",
    "            if d[head.val] > 1:\n",
    "                pr.next = head.next\n",
    "            else:\n",
    "                pr = pr.next\n",
    "            head = head.next\n",
    "        return w.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        p=head\n",
    "        q=dummy=ListNode()\n",
    "        while p:\n",
    "            if dic[p.val]==1:\n",
    "                q.next=p\n",
    "                q=q.next\n",
    "                p=p.next\n",
    "            else:\n",
    "                p=p.next\n",
    "        q.next=None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        count = {}\n",
    "        p = head\n",
    "        while p:\n",
    "            if p.val not in count:\n",
    "                count[p.val] = 1\n",
    "            else:\n",
    "                count[p.val] += 1\n",
    "            p = p.next\n",
    "        dummy = ListNode(next = head)\n",
    "        \n",
    "        p = dummy\n",
    "        while p:\n",
    "            unique = p.next\n",
    "            while unique and count[unique.val] > 1:\n",
    "                unique = unique.next\n",
    "            p.next = unique\n",
    "            p = p.next\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=p=ListNode()\n",
    "        p.next=head\n",
    "        while p and p.next:\n",
    "            if dic[p.next.val]!=1:\n",
    "                p.next=p.next.next\n",
    "            else:\n",
    "                p=p.next\n",
    "        return q.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dic = defaultdict(int)\n",
    "        curr = head\n",
    "        while curr:\n",
    "            dic[curr.val] += 1\n",
    "            curr = curr.next\n",
    "        dummy = ListNode(0, head)\n",
    "        curr = dummy\n",
    "        while curr and curr.next:\n",
    "            while curr.next and dic[curr.next.val] >= 2:\n",
    "                curr.next = curr.next.next\n",
    "            curr = curr.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        p=head\n",
    "        dic=defaultdict(int)\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        slow=dummy=ListNode()\n",
    "        dummy.next=head\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                slow.next=head\n",
    "                slow=slow.next\n",
    "            head=head.next\n",
    "        slow.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        p=head\n",
    "        cnt=defaultdict(int)\n",
    "        while p:\n",
    "            cnt[p.val]+=1\n",
    "            p=p.next\n",
    "        while head and cnt[head.val]>1:\n",
    "            head=head.next\n",
    "        if not head:\n",
    "            return head\n",
    "        p=head\n",
    "        while p.next:\n",
    "            if cnt[p.next.val]>1:\n",
    "                p.next=p.next.next\n",
    "            else:\n",
    "                p=p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        mp = {}\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val not in mp:\n",
    "                mp[cur.val] = 1\n",
    "            else:\n",
    "                mp[cur.val] += 1\n",
    "            cur = cur.next\n",
    "        ans = ListNode(0, head)\n",
    "        cur = ans\n",
    "        while cur and cur.next:\n",
    "            if mp.get(cur.next.val) > 1:\n",
    "                cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dup = set()\n",
    "        pre = set()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in pre:\n",
    "                dup.add(cur.val)\n",
    "            pre.add(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        ans = ListNode(-1)  # 哨兵节点\n",
    "        node = ans\n",
    "        while head:\n",
    "            if head.val not in dup:\n",
    "                tmp = head.next\n",
    "                head.next = None\n",
    "                node.next = head\n",
    "                node = node.next\n",
    "                head = tmp\n",
    "            else:\n",
    "                head = head.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        # if not head or not head.next:\n",
    "        #     return head\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=dummy=ListNode()\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                q.next=head\n",
    "                q=q.next\n",
    "            head=head.next\n",
    "        q.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=p=ListNode()\n",
    "        p.next=head\n",
    "        while p and p.next:\n",
    "            if dic[p.next.val]!=1:\n",
    "                p.next=p.next.next\n",
    "            else:\n",
    "                p=p.next\n",
    "        return q.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        # if not head or not head.next:\n",
    "        #     return head\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=dummy=ListNode()\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                q.next=head\n",
    "                q=q.next\n",
    "            head=head.next\n",
    "        q.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        p=head\n",
    "        dic=defaultdict(int)\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        slow=dummy=ListNode()\n",
    "        dummy.next=head\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                slow.next=head\n",
    "                slow=slow.next\n",
    "            head=head.next\n",
    "        slow.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        count = dict()\n",
    "        p = head\n",
    "\n",
    "        while p:\n",
    "            count[p.val] = count.get(p.val, 0) + 1\n",
    "            p = p.next \n",
    "        \n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head \n",
    "\n",
    "        p = dummy\n",
    "        while p:\n",
    "            unique = p.next\n",
    "\n",
    "            while unique and count[unique.val] > 1:\n",
    "                unique = unique.next\n",
    "            p.next = unique\n",
    "            p = p.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        count = {}\n",
    "        p = head\n",
    "        while p:\n",
    "            count[p.val]  = count.get(p.val, 0) + 1\n",
    "            p = p.next\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        q = head\n",
    "        while q:\n",
    "            if count[q.val] <= 1:\n",
    "                p.next = q\n",
    "                p = p.next\n",
    "            q = q.next\n",
    "        p.next = None\n",
    "        return dummy.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        tab = set()\n",
    "        p = head\n",
    "        res = set()\n",
    "        while p:\n",
    "            if p.val in tab:\n",
    "                res.add(p.val)\n",
    "            else:\n",
    "                tab.add(p.val)\n",
    "            p = p.next\n",
    "        \n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        q = head\n",
    "\n",
    "        while q:\n",
    "            if q.val not in res:\n",
    "                p.next = q\n",
    "                p = p.next\n",
    "            q = q.next\n",
    "        p.next = None\n",
    "        return dummy.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        p=head\n",
    "        dic=defaultdict(int)\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        slow=dummy=ListNode()\n",
    "        dummy.next=head\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                slow.next=head\n",
    "                slow=slow.next\n",
    "            head=head.next\n",
    "        slow.next=None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self,head:ListNode)->ListNode:\n",
    "        # if not head or not head.next:\n",
    "        #     return head\n",
    "        dic=defaultdict(int)\n",
    "        p=head\n",
    "        while p:\n",
    "            dic[p.val]+=1\n",
    "            p=p.next\n",
    "        q=dummy=ListNode()\n",
    "        while head:\n",
    "            if dic[head.val]==1:\n",
    "                q.next=head\n",
    "                q=q.next\n",
    "            head=head.next\n",
    "        q.next=None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dup = set()\n",
    "        pre = set()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in pre:\n",
    "                dup.add(cur.val)\n",
    "            pre.add(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        ans = ListNode(-1)\n",
    "        node = ans\n",
    "        while head:\n",
    "            if head.val not in dup:\n",
    "                tmp = head.next\n",
    "                head.next = None\n",
    "                node.next = head\n",
    "                node = node.next\n",
    "                head = tmp\n",
    "            else:\n",
    "                head = head.next\n",
    "        return ans.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dup = set()\n",
    "        pre = set()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in pre:\n",
    "                dup.add(cur.val)\n",
    "            else:\n",
    "                pre.add(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        ans = ListNode(-1)\n",
    "        node = ans\n",
    "        while head:\n",
    "            if head.val in dup:\n",
    "                head = head.next\n",
    "            else:\n",
    "                tmp = head.next\n",
    "                head.next = None\n",
    "                node.next = head\n",
    "                node = node.next\n",
    "                head = tmp\n",
    "\n",
    "\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        dup = set()\n",
    "        pre = set()\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in pre:\n",
    "                dup.add(cur.val)\n",
    "            else:\n",
    "                pre.add(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        ans = ListNode(-1)\n",
    "        node = ans\n",
    "        while head:\n",
    "            if head.val in dup:\n",
    "                head = head.next\n",
    "            else:\n",
    "                tmp = head.next\n",
    "                head.next = None\n",
    "                node.next = head\n",
    "                node = node.next\n",
    "                head = tmp\n",
    "\n",
    "\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "import collections\n",
    "class Solution:\n",
    "    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:\n",
    "        temp_head = head\n",
    "        nums = []\n",
    "        dummy_head = ListNode(0)\n",
    "        dummy_head.next = head\n",
    "        while temp_head:\n",
    "            nums.append(temp_head.val)\n",
    "            temp_head = temp_head.next\n",
    "        hash_list = collections.Counter(nums)\n",
    "        prev_head = dummy_head\n",
    "        while head:\n",
    "            if hash_list[head.val] != 1:              \n",
    "                prev_head.next = head.next\n",
    "                head = head.next\n",
    "            else:\n",
    "                prev_head = head\n",
    "                head = head.next\n",
    "        return dummy_head.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
